﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Task5
{
    public class Graph
    {
        private int[][] childNodes;
        private bool[] visited;

        private List<int> currentPath;
        private List<List<int>> foundCycles;

        public Int32 NodesCount
        {
            get
            {
                return this.childNodes.Length;
            }
        }

        public Int32[][] Childs
        {
            get
            {
                return this.childNodes;
            }
        }

        public Graph(int[][] nodes)
        {
            this.childNodes = nodes;
            this.visited = new bool[childNodes.GetLength(0)];
            this.currentPath = new List<int>();
            this.foundCycles = new List<List<int>>();

        }

        private void FindAllCycles(int startNode)
        {
            if (visited[startNode])
            {
                AddPath(currentPath);
            }
            else
            {
                visited[startNode] = true;

                foreach (int node in childNodes[startNode])
                {
                    currentPath.Add(node);
                    FindAllCycles(node);
                    currentPath.RemoveAt(currentPath.Count - 1);
                }

                visited[startNode] = false;
            }
        }

        private void AddPath(List<int> path)
        {
            List<int> lstPath = new List<int>();
            if (path[0] != path[path.Count - 1])
            {
                return;
            }
            foreach (int node in path)
            {
                lstPath.Add(node);
            }

            foundCycles.Add(lstPath);
        }

        public void PrintAllCycles()
        {
            for (int node = 0; node < childNodes.GetLength(0); node++)
            {
                currentPath.Add(node);
                FindAllCycles(node);
                currentPath.RemoveAt(currentPath.Count - 1);
            }

            foreach (List<int> lstPath in foundCycles)
            {
                foreach (int node in lstPath)
                {
                    Console.Write(node + " ");
                }
                Console.WriteLine();
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph g = new Graph(new int[][] {
                                              new int[] {3, 6}, // successors of vertice 0
                                              new int[] {2, 3, 4, 5, 6}, // successors of vertice 1
                                              new int[] {1, 4, 5}, // successors of vertice 2
                                              new int[] {0, 1, 5}, // successors of vertice 3
                                              new int[] {1, 2, 6}, // successors of vertice 4
                                              new int[] {1, 2, 3}, // successors of vertice 5
                                              new int[] {0, 1, 4}  // successors of vertice 6
                                            });

            bool[] visited = new bool[g.NodesCount];

            g.PrintAllCycles();
        }
    }
}
